package com.lzj.java0419;

/**
 * 面向对象的思想进行快速排序
 * 
 * 创建一个对象，让该对负责快速排序的任务（行为）
 * 
 * 如果其他类需要进行快速排，则不需要再自己实现快速排序的行为，直接调用该类的快拍行为即可
 * 
 * @author Administrator
 *
 */
public class QuickSortWomen {
	// 属性--被排序的数组
	private int[] arrSort; 

	/**
	 * 快排行为
	 */
	public void doQuickSort() {
		// 调用子方法对 属性 arrSort进行排序
		quickSort(arrSort, 0, arrSort.length - 1);
	}

	/**
	 * 打印数组的元素
	 * 
	 * @param arr
	 *            被打印的数组
	 */
	public void printArr() {
		// 使用foreach打印数组内容
		System.out.println("数组的元素为：");
		for (int i : arrSort) {
			System.out.print("   " + i);
		}
		// 换行
		System.out.println();
	}

	public int[] getArrSort() {
		return arrSort;
	}

	public void setArrSort(int[] arrSort) {
		this.arrSort = arrSort;
	}

	/**
	 * 快速排序算法
	 * 
	 * @param arr
	 *            被快排的数组
	 * @param left
	 *            快排开始的左侧下标
	 * @param right
	 *            快排开始的右侧下标
	 */
	private void quickSort(int[] arr, int left, int right) {
		// 递归结束条件
		if (left >= right) {
			// 分治结束
			return;
		}

		// 分治处理
		// 1、选取分治部分的集合的第一个元素作为标准值
		int stardVal = arr[left];
		// 设置左右查找位置的临时变量
		// 从右往左找的位置标识
		int r = right;
		// 从左往右找的位置标识
		int l = left;
		// 多次进行左右交换，依照标准值进行左右的大小分区
		while (l < r) {

			// 2、分治处理过程
			// 2.1 从右向左找第一个比标准值小的数
			while (r > l && arr[r] > stardVal) {
				// 更改循环因子
				r--;
			}
			// 将找到的比标准值小的数放到左侧空余位置（第一次放置的位置是标准值的位置）
			arr[l] = arr[r];
			// 2.2 从左往右找第一个比标准值大的数
			while (r > l && arr[l] < stardVal) {
				// 更改循环因子
				l++;
			}
			// 将找到的比标准值小的数放到左侧空余位置
			arr[r] = arr[l];
		}
		// 分治处理完成以后，将标准值放到相遇的位置
		arr[l] = stardVal;

		// 递归处理左右两部分
		// 递归左半部分
		quickSort(arr, left, l - 1);

		// 递归右半部分
		quickSort(arr, l + 1, right);
	}

}
